1. Field of the Invention
The present invention relates generally to a method for an operating system to build and maintain sectioned, ordered queues to achieve a reduction in operating costs when traversing these queues and manipulating their queue entries. More particularly, the present invention relates to a more efficient method for an operating system to recover real storage from an address space for potential use in another address space. In this application, the queues that represent the real storage in use by an address space are very long queues.
2. Description of the Related Art
Typically, in operating systems that support multiple virtual address spaces and that have the ability to support more virtual addresses (hereinafter referred to as pages) than can be backed simultaneously by real storage addresses (hereinafter referred to as frames), it is sometimes necessary to reallocate the use of a frame to a different address space. This technique is called paging and allows the operating system to reclaim a subset of the resources of one address space and use that subset for immediate operations in another address space. When the system needs to reference or update a page, a frame is obtained and the dynamic address translation tables for that page are updated using a process called xe2x80x98backingxe2x80x99, which indicates that real memory is associated with that page.
This process is described for the IBM OS/390 operating system in such publications as the IBM Redbooks ABCs of OS/390 System Programming Volume 1, SG24-5597-00, pages 43-71 (April 2000), and OS/390 Version 2 Release 10 Implementation, SG24-5976-00, pages 9-34 (March 2001), both of which are incorporated herein by reference. Referring to FIG. 1, when an instance 10 of the OS/390 operating system (OS) needs frames to back a virtual storage request, it goes to a queue 12 of available frames 14 to satisfy the request. A system resource manager (SRM) 18 checks periodically to ensure that there are a reasonable number of frames on this queue 12 for this purpose. OS instance 10 maintains an in-use frame queue 12 for each separate address space 16. If the SRM 18 detects a shortage, it uses a least recently used (LRU) algorithm to determine which in-use frames in the system are the best candidates to be reclaimed in order to replenish the supply of available frames. (Using this algorithm, frames that have not recently been referenced are the best candidates to be reclaimed.) This process for reclaiming frames is hereinafter referred to as stealing.
A real storage manager (RSM) 20 identifies how recently a frame has been referenced by maintaining an unreferenced interval count (UIC) value for each frame in use by an address space. 16 In order for the system to more quickly identify which frames are the best candidates to steal, the real storage manager (RSM) 20 maintains the address space frame queues in UIC order, with the least recently referenced frames at the beginning of the queue 12. Periodically, the RSM 20 performs update processing, which determines whether frames have been referenced, and if so, moves them to the end of the frame queue 12. Upon completion of the update processing, the least recently referenced frames remain at the beginning of the queue 12 with their UIC values incremented by a constant value and the most recently referenced frames are at the end of the frame queue 12 with their UIC values reset to zero.
The SRM 18 selects the targeted address spaces 16 to steal from, and also indicates a minimum UIC value which a frame to be stolen from any targeted frame queue 12 can have. The SRM 18 also specifies the total number of frames required to satisfy the steal request. The RSM steal processing then attempts to satisfy the SRM""s request by traversing the indicated address spaces"" frame queues and selecting the frames that meet the SRM""s UIC steal criteria. The RSM steal processing also makes one last check to determine whether or not a frame has been recently referenced, and, like the RSM UIC update process, moves any referenced frames to the end of the frame queue 12 with their UIC values reset to zero. If the RSM steal process is unable to fully satisfy the SRM""s request, the SRM 18 may elect to create a new steal request with different parameters, and this process may repeat itself until the system""s needs for frames is satisfied.
With new advances in hardware design, a larger virtual storage area is made available to address spaces 16 in an operating system. The typical approach of keeping the frame queues associated with an address space 16 in a linear structure may cause system performance degradation when traversing the queues. In a multitasking environment, processing such a queue 12 requires resource serialization which may prevent other processes from being dispatched or may even cause abnormal task termination if the processing of the longer queue 12 exceeds the system""s specified time-out intervals. The RSM UIC update and RSM UIC steal processes may no longer perform their functions effectively when traversing or manipulating the frame queues which represent this larger virtual storage area.
In general, the present invention contemplates a method and apparatus for maintaining a queue in an information handling system, in which there are defined a plurality of queue sections arranged in order from a first queue section to a last queue section. Each of the queue sections contains one or more queue entries arranged in order from a first queue entry to a last queue entry. A weight factor is defined for each queue section and for each queue entry in the queue sections. Each of the queue entries has an effective weight factor formed by combining the weight factor defined for the queue section with the weight factor defined for the queue entry.
The queue entries may correspond to available storage locations, in particular ranges of real storage addresses. The effective weight factor for such a queue entry represents an amount of time the storage location corresponding to the entry has not been referenced.
A new entry is added to the last queue section to indicate a newly available corresponding storage location, while one or more queue entries having at least a predetermined effective weight factor and corresponding to storage locations that have not been referenced in a previous time interval are deleted from the first queue section to indicate that the corresponding storage locations are no longer available.
Periodically, the effective weight factors of the queue entries are updated in accordance with whether the corresponding storage locations have been referenced. This is done by incrementing the effective weight factors of queue entries corresponding to storage locations that have not been referenced in a previous time interval and resetting the effective weight factors of queue entries corresponding to storage locations that have been referenced in a previous time interval. During such updating, the queue entries are maintained in the sections in order of their effective weight factors. Preferably, the individual weight factor defined for each queue entry in the first queue section is updated in accordance with whether the corresponding storage location has been referenced, while only the weight factor defined for each remaining queue section is updated without updating the individual weight factor defined for each queue entry in such remaining queue section. Each queue entry in the first queue section corresponding to a referenced storage location is moved to another section.
Preferably, the number of queue entries in each of the queue sections is maintained within a predetermined permissible range defined for the queue sections, by moving queue entries between queue sections and creating or deleting sections as needed. The weight factors defined for the moved queue entries are adjusted so that their effective weight factors in the new queue section are the same as their effective weight factors in the old queue section.
In a computing system having address spaces using large amount of virtual storage, the number of entries on the system resource queues used to maintain and control the amount of virtual storage, namely the real storage frame queues, becomes proportionally larger. The operating costs of maintaining order of the queue entries, traversing the queue and manipulating queue entries can be reduced by organizing the long queue into sections of fixed maximum and minimum number of entries and assigning a weight factor to each of the sections as well as individual queue entries. The sections are ordered by their weight factors and queue manipulation processing can be performed on a section by section basis determined by the section""s weight factor. This queue structure is hereinafter referred to as a sectioned ordered queue.
A weight factor update process is defined to ensure queue elements and their sections are ordered by their weight factors, which represent the length of time that the entries remain on the queue. Using a least recently used (LRU) algorithm, the process periodically increases the weight factors of the entries that have not been recently referenced. Over time, the longer a queue entry has not been referenced, the higher its weight factor value is. The weight factor provides a simple way to determine how long an entry has been on the queue without being referenced. The entries are then ordered in descending order of their weight factor values so that entries with highest weight factor values are on the oldest section of the queue. This process also ensures that the oldest section of the queue contains at least the minimum allowable number of entries. Such sections are prime candidates for other queue manipulation processes available in the computing system. The weight factor update process is initiated by the system resource manager at fixed intervals throughout the course of system operation.
There are times when the system resource manager needs to steal back some of the queue entries that have not been referenced to be reused. A queue entry steal process is defined to examine the queues in selected address spaces in the computing system. Since the queue entries had been kept in descending order of their weight factor values by the weight factor update process, the entry steal process only needs to look at the first section of the queue to find entries that had not been recently referenced, thus they are good candidates for stealing. Since the oldest sections of the queues are already containing the maximum number of entries, the entry steal process is more likely to find enough entries for stealing from these sections without having to traverse through all sections of the queues.
Another process that is also an integral part of maintaining a sectioned ordered queue is the process of merging two sections of the queue. The merging process can be initiated any time by any other processes in the computing system. The process examines pairs of adjacent queue sections from the youngest section to the oldest section. When a pair of sections can be merged without exceeding the maximum number of allowable entries, the entries from the smaller section are moved to the longer section. The weight factors of the entries being moved are then adjusted so that their effective weight factors in relation to their new section remain the same as their effective weight factors on the original queue section.
The structure of the sectioned ordered queue and previously described queue manipulation processes can be used to implement various data structures in a computing system. One such structure is the priority dispatching queue, where processes are put on the queue waiting to be dispatched based on their times spent on the queue, or their ages. The weight factors for entries of such queue is the ages of the entries on the queue.